#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<conio.h>
typedef struct lista
{
	char c;
	char v[32];
	int i;
	lista * next;
}lista;
lista *l=NULL,*o,*k,*ll=NULL;
typedef struct nod
{
int freq;
char c;
nod *next;
nod *left;
nod *right;
}nod;
nod *head=NULL,*q,*z,*p,*aux;
char y[32],i;
void AfisareCompresie(char sir [1024])
{
	int j,h,g;
	double min,max;
	j=strlen(sir);
	h=0;
	min=0;
	while(sir[h])
	{
		i=sir[h];
		o=l;
		while(o)
		{
			if(o->c==i)
			{
				min=min+o->i;
			}
			o=o->next;
		}
		h++;
	}
	max=strlen(sir)*8;
	printf("Rata de compresie este: %f\n",min/max);
}
void Decodare(FILE *fff,FILE *ffff)
{
	char c,sirul[16],ce[2];
	int adev,j;
	adev=0;
	
	for(j=0;j<16;j++)
		sirul[j]='$';
	
	while(!feof(fff))
	{
		o=ll;
		c=fgetc(fff);
		ce[0]=c;
		j=0;
		while(sirul[j]!='$')
			j++;
		sirul[j]=ce[0];
		j=0;
		adev=1;
		while(j<o->i)
		{
			if(o->v[j]!=sirul[j])
				adev=0;
			j++;
		}
		if(adev==1)
		{
			printf("%c",o->c);
			fprintf(ffff,"%c",o->c);
			for(j=0;j<16;j++)
				sirul[j]='$';
			adev=0;
		}
		else
		{
			while((o->next)&&(adev==0))
			{
				o=o->next;
				adev=1;
				j=0;
				while(j<o->i)
				{
					if(o->v[j]!=sirul[j])
						adev=0;
					j++;
				}
				if(adev==1)
				{
					printf("%c",o->c);
					fprintf(ffff,"%c",o->c);
					for(j=0;j<16;j++)
						sirul[j]='$';
					adev=0;
				}
			}
		}
		
	}
}
void AfisareCheie()
{
	int j;
	o=ll;

	printf("%c ",o->c);
	printf("%s",o->v);
	printf("\n");

	while(o->next)
	{
		o=o->next;
		printf("%c ",o->c);
		printf("%s",o->v);
		printf("\n");
	}
}
void CitireCheie(FILE *ff)
{
	char x[32],*u,*t;
	while(!feof(ff))
	{
		o=(lista*)malloc(sizeof(lista));
		if(ll==NULL)
		{
			ll=o;
			//t=fgetc(ff);
			//o->c=t;
			fgets(x,31,ff);
			if(x!=NULL)
			{
			t=strtok(x," ");
			if(t[0]=='$')
				o->c=' ';
			else
				o->c=t[0];
			t=strtok(NULL," ,\n");
			strcpy(o->v,t);
			o->i=strlen(t);
			o->next=NULL;
			}
		}
		else
		{
			k=ll;
			while(k->next!=NULL)
			{
				k=k->next;
			}
			fgets(x,64,ff);
			if((x!=NULL)&&(x[0]!=' '))
			{
				k->next=o;
				t=strtok(x," ,\n");
				if(t[0]=='$')
					o->c=' ';
				else
					o->c=t[0];
				t=strtok(NULL," ,\n");
				strcpy(o->v,t);
				o->i=strlen(t);
				o->next=NULL;
			}
		}
	}
}
void Codare(FILE *ff,FILE *fff,char sir[1024])
{
	int j;
	o=l;
	char x;
	
	
	x=o->c;
	if(x==' ')
		fprintf(ff,"$ ");
	else
		fprintf(ff,"%c ",x);

	for(j=1;j<=o->i;j++)
		{
			
			fprintf(ff,"%c",o->v[j]);
		}
		
		fprintf(ff,"\n");

	while(o->next)
	{
		o=o->next;
		x=o->c;
		if(o->c==' ')
			fprintf(ff,"$ ");
		else
			fprintf(ff,"%c ",x);

		for(j=1;j<=o->i;j++)
		{
			
			fprintf(ff,"%c",o->v[j]);
		}
		
		if(o->next)
		fprintf(ff,"\n");
		
	}

	int h,g;
	j=strlen(sir);
	h=0;
	while(sir[h])
	{
		i=sir[h];
		o=l;
		while(o)
		{
			if(o->c==i)
			{
				for(g=1;g<=o->i;g++)
				{
					fprintf(fff,"%c",o->v[g]);
					
				}
			}
			o=o->next;
		}
		h++;
	}

}
void AfisareCodSir(char sir[1024])
{
	int j,h,g;
	j=strlen(sir);
	h=0;
	while(sir[h])
	{
		i=sir[h];
		o=l;
		while(o)
		{
			if(o->c==i)
			{
				for(g=1;g<=o->i;g++)
				printf("%c",o->v[g]);
			}
			o=o->next;
		}
		h++;
	}

}
void AfisareCod()
{
	int j;
	o=l;

	printf("%c ",o->c);

	for(j=1;j<=o->i;j++)
		{
			printf("%c",o->v[j]);
		}
		printf("\n");

	while(o->next)
	{
		o=o->next;
		printf("%c ",o->c);
		for(j=1;j<=o->i;j++)
		{
			printf("%c",o->v[j]);
		}
		printf("\n");
		
	}
}
void ParcurgereArbore(nod * c)
{	
	int j; 

	if(c)
	{
		if(c->left==NULL&&c->right==NULL)
		{
			o=(lista*)malloc(sizeof(lista));
			if(l==NULL)
			{
				l=o;
				o->next=NULL;
				o->c=c->c;
				for(j=0;j<=i;j++)
				{
					o->v[j]=y[j];
				}
				o->i=i;
			
			}
			else
			{
				k=l;
				while(k->next)
				{
					k=k->next;
				}
				k->next=o;
				o->next=NULL;
				o->c=c->c;
				for(j=0;j<=i;j++)
				{
					o->v[j]=y[j];
				}
				o->i=i;
			
			}

		}
		i++;
		y[i]='0';
		ParcurgereArbore(c->left);
		y[i]='1';
		ParcurgereArbore(c->right);
		i--;
	}
	
}
void CreareArbore()
{	
	int t=0;
	
	if(head==NULL)
	{
		printf("Eroare: Head = NULL");
		return;
	}
	
	if(head->next==NULL)
	{
		printf("Eroare: Head->next = NULL");
		return;
	}
		
	do
	{
		q=head;
		z=q->next;
		aux=(nod*)malloc(sizeof(nod));
		aux->right=z;
		aux->left=q;
		head=head->next->next;
		aux->c='*';
		aux->freq=(q->freq+z->freq);
		aux->next=NULL;
		q=head;
		t=0;

		if(q==NULL)
		{
			head=aux;
		}
		else
		{
			if(q->next==NULL)
			{
				if(q->freq>aux->freq)
				{
					z=q;
					head=aux;
					head->next=z;
					t=1;
				}
				else
				{
					head->next=aux;
					t=1;
				}
			}
			else
			{
				while(q)
				{
					if(((q->freq)>(aux->freq))&&(t==0))
					{
						if(q==head)
						{
							z=q;
							head=aux;
							head->next=z;
							t=1;
						}
						else
						{
							p=head;
							while(p)
							{
								if(p->next==q && t==0)
								{
									aux->next=q;
									p->next=aux;
									t=1;
								}
								p=p->next;
							}
						}
					}
					q=q->next;
				}
				if(t==0)
				{
					z=head;
					while(z)
					{
						if((z->next==NULL)&&(t==0))
						{
							z->next=aux;
							t=1;
						}
						z=z->next;
					}
				}
		
			}
		}
	}
	while(head->next!=NULL);
}
void OrdonareLista()
{
	int t=0,auxf;
	char auxc;
	q=NULL;
	z=q;
	do
	{
		if(q!=NULL)
			q=q->next;
	
		if(q==NULL)
			q=head;
			
		z=q;
		
		while(z->next!=NULL)
		{
			z=z->next;
			
			if((q->freq)>(z->freq))
			{
				auxf=q->freq;
				auxc=q->c;
				q->freq=z->freq;
				q->c=z->c;
				z->freq=auxf;
				z->c=auxc;
			}
		}
	}
	while(q->next->next!=NULL);
	
}
void AfisareFreq(int v[256])
{
	for(int i=0;i<256;i++)
	{
		if(v[i]!=0)
	printf("%c %d \n",i,v[i]);
	}
}
void AfisareLista()
{
	q=head;
	while(q!=NULL)
	{
		printf("%c  %d\n",q->c,q->freq);
		q=q->next;

	}

}
//void OrdonareLista(int *t)
//{
//if (*t==1)
//{	printf("Eroare:t==1\n ");
//	return;
//}
//	
//if(head==NULL)
//{	printf("Eroare:head==NULL\n");
//	return;
//}
//	
//q=head;
//z=q;
//
//while(q->next!=NULL)
//{	
//	if(q->next==NULL)
//	{
//	printf("Eroare:q->next==NULL(1)\n");
//	return;
//	}
//	
//	z=q->next;
//
//	while(z->next!=NULL)
//	{		
//		if(q->next->freq>z->freq)
//		{
//			aux=q->next;
//			q->next=q->next->next;
//			aux->next=z->next;
//			z->next=aux;
//			OrdonareLista(t);
//		}
//		else
//		{
//			z=z->next;
//		}
//	}
//	if(q->next==NULL)
//	{
//	printf("Eroare:q->next==NULL(2)\n");
//	return;
//	}
//	
//	q=q->next;
//}
//*t=1;
//}
void CreareLista(int v[256])
{
	int i,j;
	char ch;
	
	for(i=0;i<256;i++)
	{
		if(v[i]!=0)
		{
			if(head==NULL)
			{
				
				q=(nod*)malloc(sizeof(nod));
				q->freq=v[i];
				q->c=(char)(i);
				q->left=NULL;
				q->right=NULL;
				q->next=NULL;
				head=q;
			}
			else
			{
				z=head;
				while(z->next!=NULL)
					z=z->next;
				

			q=(nod*)malloc(sizeof(nod));
			q->freq=v[i];
			q->c=(char)(i);
			q->left=NULL;
			q->right=NULL;
			q->next=NULL;
			z->next=q;
			}
		}
	}

}
void Frecventa (char *sir,int v[256])
{
	int i=0,x;
	while(sir[i]!=NULL)
	{
		x=sir[i];
		v[x]++;
		i++;
	}
}
void Citire(FILE *f,char *sir)
{
	char aux[1024];

while(!feof(f))
{
	fgets(aux,1024,f);
	strcat(sir,aux);
}
}

void main()
{
	char meniu,sir[1024],test[]="Acest sir este un sir test folosit pentru a demonstra functionarea corecta a acestui program";
	FILE *f= fopen("initial.txt","r");
	FILE *ff= fopen("cheie.txt","r+t");
	FILE *fff=fopen("codat.txt","r+t");
	FILE *ffff=fopen("Decodat.txt","r+t");
	int v[256],w[256],i,t=0;
	for(i=0;i<256;i++)
	{
		v[i]=0;
		w[i]=0;
	}
	
	*sir=NULL;

	Citire(f,sir);
	Frecventa(sir,v);
	CreareLista(v);
	OrdonareLista();
	CreareArbore();
	ParcurgereArbore(head);

	
while(1)

{
	
	printf("\n Pentru urmatoarele actiuni apasati\n");
	/*printf("1. Introducerea unui sir de caractere\n");
	printf("2. Folosire sir de caractere de test\n");
	printf("3. Afisare sir\n");
	printf("4. Frecventa sir\n");
	printf("5. Creare lista\n");
	printf("6. Ordonare lista\n");
	printf("7. Afisare lista \n");
	printf("8. Afisare freq\n");
	printf("9. Creare Arbore \n");
	printf("0. Generare cod \n");*/
	printf("a. Afisare cod pentru fiecare caracter\n");
	printf("s. Afisare cod pentru sirul introdus\n");
	printf("f. Afisare rata de compresie\n");
	printf("c. Codare\n\n");
	printf("Pentru urmatoarele actiuni va\n rugam sa rulati din nou programul\n pentru a se salva madificarile facute anterior in fisiere\n\n");
	printf("v. Citire cheie\n");
	printf("b. Afisare cheie\n");
	printf("d. Realizati decodarea\n");
	printf("e. Exit\n");

	meniu=getch();
			
			switch (meniu)
				{
					/*case '1' :
								system("cls");
							    Citire(f,sir);
							   break;
					case '2' :
								system("cls");
							    strcpy(sir,test);
							   break;
					case '3' : 
								system("cls");
								printf("%s \n",sir);
								break;
					case '4' :
								system("cls");
								Frecventa(sir,v);
								break;
					case '5' :	
								system("cls");
								CreareLista(v);
								break;
					
					case '7' :
								system("cls");
								AfisareLista();
								break;
					case '8' :
								system("cls");
								AfisareFreq(v);
								break;
					case '6' :
								system("cls");
								OrdonareLista();
								break;
					case '9' :
								system("cls");
								CreareArbore();
								break;
					case '0' :
								system("cls");
								i=-1;
								ParcurgereArbore(head);
								break;*/

					case 'a' :
								system("cls");
								AfisareCod();
								break;
								
					case 's' :
								system("cls");
								AfisareCodSir(sir);
								break;
					case 'c' :
								system("cls");
								Codare(ff,fff,sir);
								break;
					case 'f' :
								system("cls");
								AfisareCompresie(sir);
								break;

					case 'v' :
								system("cls");
								CitireCheie(ff);
								break;

					case 'b' :
								system("cls");
								AfisareCheie();
								break;
					case 'd' :
								system("cls");
								Decodare(fff,ffff);
								break;
					case 'e' :
								system("cls");
								printf("Va multumesc pentru rabdare :)");
								return;   	
				}
}
fclose(f);
fclose(ff);
fclose(fff);
fclose(ffff);
}